package com.a;

import com.algorithm.ListNode;

import java.util.*;

/**
 * @author: sun.hongliang
 * @create: 2020/06/30 15:22
 */
public class A6 {

    public static void main(String[] args) {
        A6 d = new A6();
        System.out.println(d.letterCombinations("23"));
    }

    public String convert(String s, int numRows) {
        if (numRows == 0) return s;
        StringBuilder[] sbs = new StringBuilder[numRows];
        for (int i = 0; i < sbs.length; i++) {
            sbs[i] = new StringBuilder();
        }
        char[] chars = s.toCharArray();
        int flg = -1;
        int l = 0;
        for (int i = 0; i < chars.length; i++) {
            sbs[l].append(chars[i]);
            if (l == numRows - 1 || l == 0) {
                flg = -flg;
            }
            l += flg;
        }
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < sbs.length; i++) {
            res.append(sbs[i].toString());
        }
        return res.toString();
    }

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        Set<Integer> sets = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (sets.contains(nums[i])) {
                return true;
            }
            sets.add(nums[i]);
            if (sets.size() > k) {
                sets.remove(nums[i - k]);
            }
        }
        return false;
    }

    public int maxArea(int[] height) {
        int i = 0;
        int j = height.length - 1;
        int res = Integer.MIN_VALUE;
        while (i < j) {
            if (height[i] < height[j]) {
                res = Math.max(res, (j - i) * height[i]);
                i++;
            } else {
                res = Math.max(res, (j - i) * height[j]);
                j--;
            }
        }
        return res;
    }

    Map<Character, String> map = new HashMap<Character, String>() {
        private static final long serialVersionUID = -6840311775447798964L;

        {
            put('2', "abc");
            put('3', "def");
            put('4', "ghi");
            put('5', "jkl");
            put('6', "mno");
            put('7', "pqrs");
            put('8', "tuv");
            put('9', "wxyz");
        }
    };

    public List<String> letterCombinations(String digits) {
        List<String> res = new LinkedList<>();
        com("", digits, res);
        return res;
    }

    private void com(String pre, String nextDig, List<String> res) {
        if (nextDig.length() == 0) {
            res.add(pre);
            return;
        }
        String numStr = map.get(nextDig.charAt(0));
        String nextDigStr = nextDig.substring(1);
        for (int i = 0; i < numStr.length(); i++) {
            char c = numStr.charAt(i);
            com(pre + c, nextDigStr, res);
        }
    }

    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode l = first;
        ListNode f = first;
        for (int i = 0; i < n; i++) {
            f = f.next;
        }
        while (f.next != null) {
            f = f.next;
            l = l.next;
        }
        ListNode t = l.next;
        if (t == null) {
            l.next = null;
        } else {
            l.next = t.next;
            t.next = null;
        }
        return first.next;
    }

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode first = new ListNode(-1);
        ListNode t = first;
        ListNode p = l1;
        ListNode q = l2;
        while (p != null && q != null) {
            if (p.val < q.val) {
                t.next = p;
                p = p.next;
            } else {
                t.next = q;
                q = q.next;
            }
            t = t.next;
        }
        if (p == null) {
            t.next = q;
        } else {
            t.next = p;
        }
        return first.next;
    }

    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode first = new ListNode(-1);
        first.next = head;
        ListNode p = head;
        ListNode h = first;
        ListNode q = p.next;
        while (p != null || q != null) {
            ListNode temp = q.next;
            h.next = q;
            q.next = p;
            p.next = temp;
            h = p;
            p = temp;
            q = temp.next;
        }
        return first.next;
    }

    public void nextPermutation(int[] nums) {
        int i = 0;
        int len = nums.length;
    }
}
